# 20210628
# Leetcode题解中Benhao的解法
# 自己写了个暴力bfs结果时间过不了

from collections import defaultdict

class solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0

        # 创建一个数据结构，来实现: stations[stop] = {buses}
        stations = defaultdict(set)
        for i, stops in enumerate(routes):
            for stop in stops:
                stations[stop].add(i)

        # 将routes转为list(set())来方便后面做差集
        routes = [set(x) for x in routes]

        # 开始BFS
        q = deque([(source, 0)])
        buses = set()
        passed = {source}

        while q:
            pos, cost = q.popleft()
            if pos == target:
                return cost

            for bus in stations[pos] - buses:
                buses.add(bus)
                for stop in routes[bus] - passed:
                    passed.add(stop)
                    q.append((stop, cost + 1))

        return -1
